#include <stdio.h>
#include <stdlib.h>
#include "list.h"


//头结点创建
int list_create_head(Head_st **ptr)
{
	*ptr = malloc(sizeof(**ptr));
	if(*ptr == NULL)
		return -1;
	(*ptr)->first = NULL;
	(*ptr)->last = NULL;
	(*ptr)->node_number = 0;
}

//给新结点赋值，选择插入方式
int list_create(Head_st **ptr,way way)
{
	list_st *newnode = NULL;
	while(1)
	{
		int num;
		scanf("%d",&num);
		if(num == -1)
			break;
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return -1;
		newnode->data = num;
		newnode->next = NULL;

		way(ptr,newnode);
	}
}

int list_insert_head(Head_st **ptr,list_st *newnode)
{
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
		(*ptr)->node_number++;
	}
	else
	{
		newnode->next = (*ptr)->first;
		(*ptr)->first = newnode;
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->node_number++;
	}
}


int list_insert_end(Head_st **ptr,list_st *newnode)
{
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
		(*ptr)->node_number++;
	}
	else
	{
		(*ptr)->last->next = newnode;
		(*ptr)->last = newnode;
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->node_number++;
	}


}

/*@prev 要插入结点的前驱
 *@cur 插入的位置
 *
 */




int list_insert_order(Head_st **ptr,list_st *newnode)
{
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
		(*ptr)->node_number++;
	}
	else
	{
		list_st *prev = NULL;
		list_st *cur = (*ptr)->first;
		while(cur)
		{
			if(cur->data > newnode->data)
			{
				break;
			}
			else
			{
				prev = cur;
				cur = cur->next;
			}
		}
		//没找到
		if(cur == NULL)
		{
			(*ptr)->last->next = newnode;
			(*ptr)->last = newnode;
		}
		else
		{
			//找到的结点为头结点		
			if(cur == (*ptr)->first)
			{
				newnode->next = (*ptr)->first;
				(*ptr)->first = newnode;
			}
			//找到的位置为中间结点			
			else
			{
				prev->next = newnode;
				newnode->next = cur;
			}
		}
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->node_number++;


	}
}




int list_display(Head_st *ptr)
{
	if(ptr == NULL)
		return -1;
	list_st *me = ptr->first;
	do
	{
		printf("%d ",me->data);
		me = me->next;
	}while(me != ptr->first);
	printf("\n");
	return 0;
}



//查找结点
list_st *list_find(Head_st *ptr,Datatype data)
{
	if(NULL == ptr)
		return NULL;
	list_st *me = ptr->first;
	do
	{
		if(data == me->data)
		{
			return me;
		}
		me = me->next;
	}while(me != ptr->first);
	if(me == NULL)
		return NULL;
}
//删除结点
int list_delete(Head_st *ptr,Datatype data)
{
	if(ptr == NULL || ptr->first == NULL)
		return -1;
	list_st *cur = ptr->first;
	list_st *prev = NULL;

	do
	{
		if(cur->data == data)
			break;
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}while(cur != ptr->first);
	if(cur == NULL)
	{
		return 0;
	}
	else
	{
		printf("%d\n",cur->data);
		if(cur == ptr->first)
		{
			ptr->first = cur->next;
			ptr->last->next = ptr->first;
		}
		else if(cur == ptr->last)
		{
			prev->next = ptr->first;
		}
		else
		{
			prev->next = cur->next;
			cur->next = NULL;
		}
		free(cur);
		ptr->node_number--;
	}
	return 0;
}
//销毁结点
int list_destroy(Head_st **ptr)
{
	list_st *me = (*ptr)->first;
	list_st *p = NULL;
	do{
		p = me->next;
		free(me);
		me = p;
	}while(p != (*ptr)->first);
	*ptr = NULL;
	free(*ptr);	
}








